// SqStack.cpp
// 栈的顺序存储表示

#include <string>

#define STACK_INIT_SIZE 100;    // 存储空间初始分配量
#define STACK_INCREMENT 10;     // 存储空间分配增量

enum Status = {
    OK,
    ERROR,
};

typedef struct STElem {
    int nData;
    string strDesc;
};

typedef struct {
    STElem *base;
    STElem *top;
    int stackSize;
}SqStack;

Status InitStack(SqStack &S)
{
    S.base = (STElem *)new SqStack[STACK_INIT_SIZE];
    if (!S)
        return ERROR;

    S.top = S.base;
    S.stackSize = STACK_INIT_SIZE;

    return OK;
}

Status DestroyStack(SqStack &S)
{
    // ??? 这个要怎么写
}

Status ClearStack(SqStack &S)
{
    // 同上
}

bool StackEmpty(SqStack S)
{
    if (!S)
        return false;

    if (S.base && S.top)
    {
        if (S.base == S.top)
        {
            return true;
        }
    }

    return false;
}

int StackLength(SqStack S)
{
    
}

Status GetTop(SqStack S, STElem &e)
{
    if (S.top == S.base)
    {
        return ERROR;
    }

    e = *(S.top - 1);

    return OK;
}

Status Push(SqStack &S, STElem &e)
{
    if (S.top - S.base >= S.stackSize)
    {
        S.base = (STElem *)realloc(S.base, (S.stackSize + STACK_INCREMENT) * sizeof(STElem));

        if (!S.base)
        {
            return ERROR;
        }

        S.top = S.base + S.stackSize;
        S.stackSize += STACK_INCREMENT;
    }

    *S.top++ = e;

    return OK;
}

Status Pop(SqStack &S, STElem &e)
{
    if (S.top == S.base)
    {
        return ERROR;
    }

    e = *(--S.top);

    return OK;
}

void conversion()
{
    // 对于输入的任意一个非负十进制证书，打印输出与其等值的八进制数。
    InitStack(S);
    scanf(" %d", N);
    while (N)
    {
        Push(S, N % 8);
        N = N / 8;
    }

    while (!StackEmpty(s))
    {
        Pop(S, e);
        printf(" %d", e);
    }
}

void LineEdit()
{
    // 利用字符栈S，从终端接收一行并传送至调用过程的数据区。
    InitStack(S);
    ch = getchar();     // 从终端接收第一个字符
    while (ch != EOF)
    {
        while (ch != EOF && ch != "\n")
        {
            switch (ch)
            {
            case '#':
                Pop(S,c);       // 仅当栈非空时退栈
                break;
            case '@':
                ClearStack(S);  // 重置S为空栈
                break;
            default:
                Push(S, ch);    // 有效字符进栈，未考虑栈满情况。
                break;
            }
        }
        ch = getchar();
    }

    // 将从栈底到栈顶的栈内字符传送至调用过程的数据区
    ClearStack(S);
    if (ch != EOF)
    {
        ch = getchar();
    }
    
    DestroyStack(S);
}

typedef struct Pos
{
    int x;
    int y;
};

typedef struct
{
    int ord;    // 通道块在路径上的序号
    Pos seat;   // 通道块在迷宫中的坐标位置
    int di;     // 从此通道块走向下一个通道块的方向
}SElemType;

bool MazePath(Pos start, Pos end)
{
    // 若迷宫中存在从入口start到出口end的通道，则求得一条存放在栈中（从栈底到栈顶），并返回TRUE，否则返回FALSE。
    SqStack *S = new SqStack;
    InitStack(*S);
    Pos curPos = start;     // 设定当前位置为入口位置
    int curStep = 1;        // 探索第一步

    do
    {
        if (Pass(curPos))   // 当前位置可通过，即是未曾走到过的通道块。
        {
            FootPrint(curPos);      // 留下足迹
            SElemType e(curStep, curPos, 1);
            Push(S, e);     // 加入路径

            if (curPos == end)      // 到达终点
            {
                return true;
            }

            curPos = NextPos(curPos, 1);    // 下一位置是当前位置的东邻
            curStep++;      // 探索下一步
        }
        else        // 当前位置不能通过
        {
            if (!StackEmpty(*S))
            {
                Pop(S, e);
                while (e.di == 4 && !StackEmpty(*S))
                {
                    MarkPrint(e.seat);      // 留下不能通过的标记
                    Pop(S, e);      // 退回一步
                }
                if (e.di < 4)
                {
                    e.di++;
                    Push(S, e);     // 换下一个方向探索
                    curPos = NextPos(e.seat, e.di);     // 设定当前位置是该方向上的相邻块
                }
            }
        }
    } while (!StackEmpty(*S));
    
    return false;
}

int EvaluateExpression()
{
    // 算术表达式求值的算法优先算法
    // 设OPTR和OPND分别是运算符栈和运算数栈，OP为运算符集合。
    InitStack(OPTR);
    Push(OPTR, '#');

    InitStack(OPND);
    c = getchar();

    while(c != '#' || GetTop(OPTR) != '#')
    {
        if(!In(c, OP))      // 不是运算符则进栈
        {
            Push(OPND, c);
            c = getchar()
        }
        else
        {
            switch(Precede(GetTop(OPTR)), c)
            {
                case '<':       // 栈顶元素优先权低
                    Push(OPTR, c);
                    c = getchar();
                    break;
                case '=':       // 脱括号并接收下一字符
                    Pop(OPTR, x);
                    c = getchar();
                    break;
                case '>':       // 退栈并将运算结果入栈
                    Pop(OPTR, theta);
                    Pop(OPND, b);
                    Pop(OPND, a);
                    Push(OPND, Operate(a, theta, b));
                    break;
            }
        }
    }

    return GetTop(OPND);
}

void hanoi(int n, char x, char y, char z)
{
    // 将塔座x上按直径由小到大且自上而下编号为1至n的n个圆盘按规则搬到塔座z上，y可用作辅助塔座。
    // 搬动操作move(x, n, z)可定义为(c是初始值为0的全局变量，对搬动计数)。
    if(n == 1)
    {
        move(x, 1, z);      // 将编号为1的圆盘从x移到z
    }
    else
    {
        hanoi(n - 1, x, z, y);      // 将x上编号为1至n-1的圆盘移到y，z作辅助塔。
        move(x, n, z);              // 将编号为n的圆盘从x移到z
        hanoi(n - 1, y, x, z);      // 将y上编号为1至n-1的圆盘移到z，x做辅助塔。
    }
    
}

